const arr = [12,8,24,16,1]

// 冒泡排序
function bubble(arr){
    let temp = null
    for(let i = 0; i < arr.length; i++){
        for(let j = 0; j < arr.length - 1 - i; j++){
            if(arr[j] > arr[j+1]){
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp

                // 无需借助第三方变量，用数组结构的方式直接互换值
                // [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
    }
    return arr
}
// const result = bubble(arr)
// console.log(result)

// 选择排序
// 跟冒泡排序的区别：冒泡排序是每次比较，如果大就交换位置；而选择排序是每次比较不交换位置，直到这一轮比较结束后，拿到最大值再跟数组最后一项交换位置。
function choose(arr){
    for(let i = 0; i < arr.length; i++){
        let currentMax = null
        let currentMaxIndex = null
        for(let j = 0; j < arr.length - i; j++){
            if(!currentMax || arr[j] > currentMax){
                currentMax = arr[j]
                currentMaxIndex = j
            }
        }
        arr[currentMaxIndex] = arr[arr.length - 1 - i]
        arr[arr.length - 1 - i] = currentMax
    }
    return arr
}
// const result = choose(arr)
// console.log(result)

// 插入排序
// 先把数组第一项插入一个新数组，拿原数组剩余的各项跟新数组中的各项对比(跟新数组从尾到头对比)，如果该项大于新数组中的某项，则把该项插到新数组某项的右边。
// 如果跟新数组从尾到头对比完了还没插进去，说明其值最小，那么就放到新数组头部第一项。
function insert(arr){ 
    let newArr = [arr[0]]
    for(let i = 1; i < arr.length; i++){
        let A = arr[i]
        for(let j = newArr.length -1; j >=0 ; j--){
             let B = newArr[j]
             if(A > B){
                 newArr.splice(j+1,0,A)
                 break
             }
             if(j === 0){
                 newArr.unshift(A)
             }
        }
    }
    return newArr
}
// const result = insert(arr)
// console.log(result)

// 快速排序
// 二分法 每次取数组中间一项 比它小的丢到左侧数组，比它大的丢到右侧数组，再依次递归左右两侧的数组，直到全排完
function quick(arr){
    if(arr.length <= 1){
        return arr
    }
    const centerIndex = Math.floor(arr.length / 20)
    const centerNum = arr[centerIndex]
    arr.splice(centerIndex,1)
    const left = []
    const right = []

    for(let i = 0; i < arr.length; i++){
       if(arr[i] > centerNum){
           right.push(arr[i])
       }else{
           left.push(arr[i])
       }
    }
    return quick(left).concat([centerNum,...quick(right)])
}
const result = quick(arr)
console.log(result)

